Non-volatile memory devices such as flash memory (“FM”), and to a lesser extent phase change memory (“PCM”), (collectively, “NVM” or non-volatile memory) are becoming increasingly popular and a real alternative to traditional devices such as hard disks. They retain the stored data as well as hard disks, but allow for much shorter access times. Moreover, they are not as susceptible to kinetic shock because of the absence of moving mechanical parts, and they allow for smaller form factors. For this, and other reasons, such devices, and in particular FM, are becoming the devices of choice for consumer grade devices such as mobile devices.
In FM, information is stored in cells in form of a trapped charge with very long leakage times (10 years or more). The charge in a cell can take one of several different levels, leading to single level or multilevel memory devices. In PCM, information is stored in the form of a state of a material. Such a state is often referred to as a phase and in PCM several discrete phases may be used to store information.
Flash memory is a subclass of electrically erasable programmable read-only memory (“EEPROM”) that is erased and programmed in large blocks. It stores information in an array of memory cells made from floating-gate transistors. These cells can store one or multiple bits of information by encoding the information into the amount of charge trapped on the floating gate. Flash memory using one-bit cells is called a single-level cell (“SLC”) device, and memory using multiple bits per cell is called a multi-level cell (“MLC”) device.
Conventional Arrangement of NVM
FIG. 1 illustrates a general model of NVM storage showing a controller 110, a page read/write (R/W) module 120, and the physical cells 130 and their corresponding R/W modules. These units are connected by signal paths 140 and 142 which allow the transmission of information between these units. In applications, these units may occupy the same physical space, or they may be separated.
In application, these units may be integrated in the same device, or in some cases the controller 110 may be integrated in a different device than the R/W module 120 and physical cells 130. An example is the case where the controller 110 is integrated in a photo camera and the R/W module 120 and physical cells 130 are integrated on the flash card where photos are stored. Unless otherwise indicated, the positions of the R/W module, cells and controller, and the type of NVM used for the cells, is not critical to understanding the details.
FIG. 2 gives further details of the structure of the cell unit 130. The unit comprises further sub-units called pages and blocks. A page, denoted by 210 in the figure, coincides with a bitline within a block. A bitline, also denoted by 210 is a series of cells arranged in one line. Wires connecting cells within a column, denoted by 230, are called wordlines. A block 220 is illustrated comprising a number of pages. Typical sizes for pages are one to four kilobytes (KB), and typical sizes for blocks are 128, 256, or 512 KB. Other parameters are also possible and depend on applications.
In some flash technologies, such as the NOR flash, the bits in the cell module 130 can be written individually, whereas in other technologies, such as the NAND flash, the bits need to be written on a page basis. In all existing flash technologies, erasing needs to be done on a block basis, i.e., to erase a single bit, the entire block 220 needs to be erased, and then reprogrammed. Generally, a block needs to be erased if the charge of a single cell within the block needs to be lowered.
FIG. 3 gives a more detailed schematic of a page. As shown there, each page might comprise cells 310 of the physical entities holding charges, and electronics used to read and write these charges. In flash memory, the charge stored on a cell alters the physical properties of the cell and the electronic components read the charge by measuring voltages or currents in the cell that depend on this physical property. When a floating gate transistor is used the amount of charge stored on the floating gate changes the threshold of the transistor. This change may be measured by the electronics. The cells are connected via the bitline 320 which in many embodiments in practice are physical wires.
The structure of an example conventional cell is further detailed in FIG. 4, showing an electronic component 410, called the R/W unit, which is responsible for reading and writing symbols from and to cell 420, which contains the actual charge. The role of the R/W Module 410 is to read the charge level in cell 420, and transform it into the bit or sequences of bits represented by that charge. Another role of the R/W Module is to change the charge level of the cell in order to change the bit or bit sequence represented by that charge.
In general, the electronics involved in the R/W Module is capable of sensing the amount of charge in cell 420, and transform this into tangible information consisting of zeros and ones. In a SLC, the charge in a cell represents only one bit. The absence of a charge, or a very low amount of charge, could be interpreted as a logical “zero”, whereas a high level of charge could be interpreted as a logical “one”. In a MLC, charges can have more than two states.
For example, in a situation where the charge level represents two bits, the absence of a charge, or a very low level of charge, could represent the sequence “00”, a charge level of 0.25 of the maximum charge level (or a charge level close to this) could represent the sequence “01”, a charge level of half the maximum charge level (or a charge level close to that) could represent the sequence “10”, and a charge level close to maximum could represent the sequence “11.”
Other interpretations of sequences based on charge levels are of course also possible and, unless otherwise indicated, are not critical to the understanding of the basic functioning of an MLC flash device. A flash device storing three bits per cell would have to compare charge levels to an absolute reference that has a resolution of one-eighth of the maximum charge level, and four bits per cell would translate to comparing charge levels to an absolute reference that has a resolution of one-sixteenth of the maximum charge level.
In a flash device, charges can only be changed in one direction until erasing occurs. For the purposes of this disclosure, and for keeping the technical discussions simple, we assume that charges can only be added to the cell. In a practical implementation, the opposite may be the case, i.e., cells start with their maximum charge, and charges are subtracted from the cell until the charge of the cell is zero, but it is to be understood that both methods are equivalent as far as the description of this invention disclosure is concerned, and that the teachings of this disclosure are equally applicable to both methods.
Once the charge of a cell reaches its maximum value, the cell cannot be rewritten anymore. At this point, the cell's content needs to be erased, and a new charge needs to be injected into the cell, representing the information. Because of the specifics of connections of bitlines and wordlines in a flash device, erasing the content can only be done on the level of a block. This slows down the speed of the write operation. Moreover, the erase operation leads to a wear of the cells, and to accelerated leakage of charge over time. Typically, the manufacturer of a flash device indicates a number of P/E (Program-Erase) cycles that a device can endure before becoming unreliable. For SLCs, this number is in the range of 100,000, whereas for MLCs, it may be as low as 5,000.
Since every write operation on a block increases the level of at least one cell in the block, this means that writing a single bit on a block of an SLC leads to a full erase of the block (on average). In order to increase the lifetime of a device, controller 110 may implement countermeasures that include leveling the wear of the various blocks by applying load balancing methods. The wear is more pronounced for MLCs, since hitting the various levels requires careful programming of charge injection, and an overshoot results in a complete erase of the block. The programming cycle needs to cautiously approach the target charge level from below, which translates into many programming cycles and will only work when the number of bits stored per cell is not large. In addition to the programming issue, MLCs also suffer from less reliability, as low memory endurance may cause a drift of threshold levels in ageing devices and hence lead to programming and read errors.
For these reasons, researchers have been looking for methods and means to rewrite cells multiple times before erasing the cell (and hence the block containing the cell). For example, [Jiang07] and some of the references cited therein introduce a scheme, called “floating codes”, which group multiple cells together to jointly record and rewrite the cells, using the controller to keep track of the number of times a cell has been rewritten. A similar technique is employed in “buffer codes” disclosed in [Bohossian]. While these techniques effectively increase the number of times cells are rewritten, in all such schemes, and more generally, in all schemes inspired by write-once-memory techniques, the charges of the different cells do not relate to one another, and it is important to program the charge levels exactly in order to enjoy the benefits of the system. Moreover, accurate references need to be generated to compare the charge levels (or proxies thereof, such as voltage or current levels) against. Moreover, gradual wear of the cell, which leads to faster leakage of charges over the lifetime of the device, could substantially impede the operation of these techniques.
A different technique that does not suffer from many of the disadvantages of the previous schemes called “rank modulation coding” has been disclosed in [Jiang09]. In this scheme, a group of cells jointly store a number of bits of information. The information is modulated via a unique permutation given by the levels of charge in the cells. The permutation defined by the charge levels in the cells is given by the permutation obtained by sorting the charge levels from top to bottom (or bottom to top—there is no significant difference).
For example, if the charge levels are 0, 1, 2, and 3, and the charges in the cells are given by 1, 0, 3, and 2, then the corresponding permutation could be (0,1)(2,3), in the standard cycle notation for permutations. If the next sequence of bits corresponds to a permutation (0,1,2,3), for example, then one could add a charge of four units to the first cell, a charge of two units to the second cell, and a charge of two units to the last cell, resulting in charge levels of [5,2,3,4]. By sorting, it can be seen that the permutation corresponding to these charges is (0,1,2,3). What is therefore important for the teachings of [Jiang09] is the relative ordering of the charges in the cells, not the absolute values of these charges.
This makes it unnecessary to have a common reference for the cells, and also, it makes it unnecessary to have exact charge levels applied to the cells. Moreover, if the cells “deflate” at similar rates, i.e., if they suffer from similar leakage properties, then the ordering of the cells stays the same and the information is not lost. However, a big disadvantage of this scheme is the complexity of rewriting.
[Jiang09] gives a number of approaches to this problem which are based on finding Gray codes in the permutation group, and are not easily implementable in practice, as they need a quick way of encoding a sequence of bits to a unique permutation, and a way of changing one permutation to another by adding a very small amount of charge to the cells. While rank modulation coding leads to a number of advantages for flash memory devices, such as an increase in the endurance of the device, resilience to common leakage of the cells, lack of efficient processes to encode the bits into charge levels, and to change the charge levels according to the incoming bit patterns makes the scheme difficult to use in practice.
Given the state of memory storage, improvements are needed.